package com.datastructures2.sort;

/**
 * @author MaoLin Wang
 * @date 2020/2/1819:53
 */
public class MergeSort {
    private static int CUTOFF = 1;

    public static <T extends Comparable<? super T>> void mergeSort(T[] arr) {
        T[] temp = (T[]) new Comparable[arr.length];
        mergeSortTopToBottom(arr, temp, 0, arr.length - 1);
      // .// mergeSortBottomToTop(arr, temp);
    }

    /**
     * 自顶向下归并排序 长度为N的数组，需要1/2NlogN到NlgN次比较
     * 优化：在数组大小小于15时使用插入排序
     * 如果a[mid]已经小于a[mid+1] 则不进行merge
     *
     * @param arr
     * @param temp
     * @param left
     * @param right
     * @param <T>
     */
    private static <T extends Comparable<? super T>> void mergeSortTopToBottom(T[] arr, T[] temp, int left, int right) {
        //System.out.println("sort(arr," + left + "," + right + ")");

        if (left < right) {
            //小于CUTOFF=15时，进行 插入排序
            if (right - left < CUTOFF) {
                InsertSort.insertSort(arr, left, right);
            }
            System.out.println("sort(arr," + left + "," + right + ")");
            int mid = (left + right) / 2;
            mergeSortTopToBottom(arr, temp, left, mid);
            mergeSortTopToBottom(arr, temp, mid + 1, right);
            //如果左半边最后一个元素大于右半边第一个元素时才进行合并
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {
                merge(arr, temp, left, mid + 1, right);

            }

        }
    }

    /**
     * 自底向上
     *
     * @param arr  原始数组
     * @param temp 临时数组
     * @param <T>
     */
    private static <T extends Comparable<? super T>> void mergeSortBottomToTop(T[] arr, T[] temp) {
        int N = arr.length;
        //一开始两两比较，gap为1，之后每次都扩大一倍
        for (int gap = 1; gap < N; gap *= 2) {
            //数组大小小于CUTOFF时，进行插入排序
            if (gap < CUTOFF) {
                for (int left = 0; left < N - gap; left += gap + gap) {
                    int right = Math.min(left + gap + gap - 1, N - 1);
                    InsertSort.insertSort(arr, left, right);
                }
            } else {
                //对0到N-gap进行排序，gap为1，就是两两排序，gap为2，就是四四排序
                for (int left = 0; left < N - gap; left += gap * 2) {
                    //计算当前待合并数组的右边界位置，如果原始数组最后一组数据不够2*gap，则left+gap*2就会越界，其真实的边界应当是N-1
                    int right = Math.min(left + gap * 2 - 1, N - 1);
                    //同自顶向下，若待合并的数据已经是有序的，则不进行合并

                    if (arr[left + gap - 1].compareTo(arr[left + gap]) > 0) {
                        merge(arr, temp, left, left + gap, right);

                    }
                }
            }


        }
    }

    /**
     * 合并两组数据
     *
     * @param arr        原始数组
     * @param temp       临时数组
     * @param leftStart  左半部分开始位置
     * @param rightStart 右半部分开始位置
     * @param rightEnd   右半部分结束位置
     * @param <T>
     */
    private static <T extends Comparable<? super T>> void merge(T[] arr, T[] temp, int leftStart, int rightStart, int rightEnd) {
        System.out.println("merge(arr,temp," + leftStart + "," + rightStart + "," + rightEnd + ")");
        //计算左半部分边界
        int leftEnd = rightStart - 1;
        //临时数组当前位置的指针
        int tempCurrent = leftStart;
        //计算待合并数组的总长度
        int length = rightEnd - leftStart + 1;
        //当任意一边数据拷贝完毕结束循环
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            if (arr[leftStart].compareTo(arr[rightStart]) <= 0) {
                temp[tempCurrent++] = arr[leftStart++];
            } else {
                temp[tempCurrent++] = arr[rightStart++];
            }
        }
        //如果是左边的未拷贝完毕，则继续将左边剩下的拷贝到临时数组
        while (leftStart <= leftEnd) {
            temp[tempCurrent++] = arr[leftStart++];
        }
        //如果是右边的未拷贝完毕，则继续将右边剩下的拷贝到临时数组
        while (rightStart <= rightEnd) {
            temp[tempCurrent++] = arr[rightStart++];
        }
        for (int i = 0; i < length; i++, rightEnd--) {
            arr[rightEnd] = temp[rightEnd];
        }
    }


    public static <T extends Comparable<? super T>> void testMergeSort(T[]arr){
        if (arr.length==0||arr.length==1) {
            return;
        }
        T [] temp=(T[])new Comparable[arr.length];
        testMergeSort(arr,temp,0,arr.length-1);
    }

    private static<T extends Comparable<? super T>> void testMergeSort(T[] arr, T[] temp, int left, int right) {
        if (right-left>=12){

            int mid=left+(right-left)/2;
            testMergeSort(arr,temp,left,mid);
            testMergeSort(arr,temp,mid+1,right);
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {

            testMerget(arr,temp,left,mid+1,right);
            }
        }else {
            InsertSort.insertSort(arr,left,right);
        }
    }

    private static<T extends Comparable<? super T>> void testMerget(T[] arr, T[] temp, int left, int rightStart, int right) {
        int leftEnd=rightStart-1;
        int length=right-left+1;

        int cur=left;
        while (left<=leftEnd && rightStart<=right){
            if (arr[left].compareTo(arr[rightStart])<0){
                temp[cur++]=arr[left++];
            }else {
                temp[cur++]=arr[rightStart++];
            }
        }
        while (left<=leftEnd){
            temp[cur++]=arr[left++];
        }
        while (rightStart<=right){
            temp[cur++]=arr[rightStart++];
        }

        for (int i = 0; i < length; i++,right--) {
            arr[right]=temp[right];
        }

    }


    public static void main(String[] args) {
    /*  Integer[]arr=new Integer[8000000];
        Random random=new Random();
        for (int i = 0; i < 8000000; i++) {
            arr[i]= random.nextInt(8000000);
        }
        long begin=System.currentTimeMillis();
        System.out.println(begin);
        mergeSortBottomToTop(arr);
        long end=System.currentTimeMillis();
        System.out.println(end);

        System.out.println(end-begin);*/
        Integer[] arr = {4, 12, 4, 25, 12, 524, 12, 12, 25, 346, 21, 346, 47, 587, 96, 4534, 21, 56, 8, 78, 9, 2, 12};
        testMergeSort(arr);
        for (Integer o : arr) {
            System.out.println(o);
        }
    }
}
